

/**
 * @description: 布隆过滤器
 * @return {*}
 */
class BloomFilter {
    constructor(size, hashFunctions, bitArray) {
        this.size = size; // 过滤器的大小
        this.bitArray = bitArray ? bitArray : new Array(size).fill(false); // 初始化位数组
        this.hashFunctions = hashFunctions; // 哈希函数列表
    }

    // 插入元素
    insert(element) {
        // 使用每个哈希函数对元素进行哈希并设置对应的位为 true
        for (let i = 0; i < this.hashFunctions.length; i++) {
            const index = this.hashFunctions[i](element) % this.size;
            this.bitArray[index] = true;
        }
    }

    // 检查元素是否存在
    contains(element) {
        // 使用每个哈希函数对元素进行哈希并检查对应的位是否为 true
        for (let i = 0; i < this.hashFunctions.length; i++) {
            const index = this.hashFunctions[i](element) % this.size;
            if (!this.bitArray[index]) {
                return false;
            }
        }
        return true;
    }
}


/**
 * @description: 哈希函数
 * @param {*} str 需要存储的数据
 * @return {*}
 */
function hashFunction(str){
    let hash = BigInt(0);
    for (let i = 0; i < str.length; i++) {
        const char = str.charCodeAt(i);
        hash = ((hash << BigInt(5)) - hash + BigInt(char)) & BigInt("0xFFFFFFFFFFFFFFFF");
    }
    return Number(hash);
}
